import numpy as np


def hungarian_algorithm_non_square(cost_matrix):
    cost_matrix = np.array(cost_matrix)
    num_workers, num_tasks = cost_matrix.shape

    # 初始化匹配结果
    from_worker = [-1] * num_tasks
    total_cost = 0

    # 减行
    for i in range(num_workers):
        row_min = cost_matrix[i].min()
        cost_matrix[i] -= row_min

        # 尝试为每个工人找到最小成本的任务，但注意我们可能无法为所有工人找到任务
    for worker in range(num_workers):
        min_cost_task = -1
        min_cost = float('inf')
        for task in range(num_tasks):
            if cost_matrix[worker][task] < min_cost and from_worker[task] == -1:  # 确保任务还未被分配
                min_cost = cost_matrix[worker][task]
                min_cost_task = task

        if min_cost_task != -1:
            from_worker[min_cost_task] = worker
            total_cost += cost_matrix[worker][min_cost_task]

            # 构建工人到任务的映射（只包含已匹配的）
    assignment = [(worker, task) for task, worker in enumerate(from_worker) if worker != -1]
    # 注意：上面的列表推导式中的元组顺序已经反转，以匹配(worker, task)的格式

    # 如果任务少于工人数，那么将有一些工人没有被分配任务
    unassigned_workers = [worker for worker in range(num_workers) if worker not in [w for _, w in assignment]]

    return total_cost, assignment, unassigned_workers


# 新的实例数据
cost_matrix = [
    [4, 1, 3, 2],  # 工人1
    [2, 0, 5, 4],  # 工人2
    [3, 2, 2, 1],  # 工人3
    [1, 1, 1, 3],  # 工人4
    [5, 6, 7, 8]  # 工人5（这个工人将不会被分配任务）
]

min_cost, assignment, unassigned_workers = hungarian_algorithm_non_square(cost_matrix)
print("Minimum cost:", min_cost)
print("Assignment:", assignment)
print("Unassigned Workers:", unassigned_workers)